\begin{frame}[allowframebreaks]
\frametitle{Regular expressions}

\begin{center}
\begin{tabular}{cc}
Ausdruck $\gamma$ & Sprache L($\gamma$) \\
$\emptyset$ & $\emptyset$ \\
$\lambda$ & $\{\lambda\}$ \\
$a (a \in \Sigma)$ & $\{a\}$ \\
$(\alpha \ominus \beta)$ & $\{\begin{matrix}u \\[-1ex] v \end{matrix} \mid u \in L(\alpha) v \in L(\beta) l_2(u) = l_2(v)\}$ \\
($\alpha$ \rotatebox{90}{$\ominus$} $\beta$) & $\{uv \mid u \in L(\alpha) v \in L(\beta) l_1(u) = l_1(v)\}$ \\
$(\alpha)^{*\ominus}$ & $\underset{i \geq 0}{\bigcup}L^{i\ominus}$ where $L^{0\ominus} = \lambda, L^{1\ominus} = L, L^{n\ominus} = L \ominus L^{(n - 1)\ominus}$ \\
$(\alpha)^{*\rotatebox{90}{$\ominus$}}$ & $\underset{i \geq 0}{\bigcup}L^{i\rotatebox{90}{$\ominus$}}$ where $L^{0\rotatebox{90}{$\ominus$}} = \lambda, L^{1\rotatebox{90}{$\ominus$}} = L, L^{n\rotatebox{90}{$\ominus$}} = L \ominus L^{(n - 1)\rotatebox{90}{$\ominus$}}$ \\
$(\alpha) \cup (\beta)$ & $L(\alpha) \cup L(\beta)$ \\
$(\alpha) \cap (\beta)$ & $L(\alpha) \cap L(\beta)$ \\
$(\alpha)^c$ & $\{w \in \Sigma^{**} \mid w \not\in L(\alpha)\}$
\end{tabular}
\end{center}

$R_1 = \{\ominus, \rotatebox{90}{$\ominus$}, *\ominus, *\rotatebox{90}{$\ominus$}, \cup, \cap, ^c\}$

$R_2 = \{\ominus, \rotatebox{90}{$\ominus$}, *\ominus, *\rotatebox{90}{$\ominus$}, \cup, \cap\}$

$R_3 = \{\ominus, \rotatebox{90}{$\ominus$}, \cup, \cap, ^c\}$

\begin{define}
	The class of languages created by $R_1$, $R_2$ and $R_3$ are denoted by $\mathcal{L}(RE)$, $\mathcal{L}(CFRE)$ (complement free) and $\mathcal{L}(SFRE)$ (star free), respectively. 
\end{define}

\end{frame}

\begin{frame}
\frametitle{Example}

\begin{Example}
$\alpha = (((a \ominus b)^{*\ominus})\rotatebox{90}{$\ominus$}((b \ominus a)^{*\ominus}))^{*\rotatebox{90}{$\ominus$}}$
\end{Example}

Then $L(\alpha)$ is the language containing "chessboards" with even side length over a and b. 

\begin{center}
\begin{tabular}{|c|c|c|c|c|c|}
\hline
a & b & a & b & a & b\\
\hline
b & a & b & a & b & a\\
\hline
a & b & a & b & a & b\\
\hline
b & a & b & a & b & a\\
\hline
\end{tabular}
\end{center}

\end{frame}

\begin{frame}
\frametitle{Properties of regular expressions}

\begin{thm}
The family of hv-local picture languages is properly included in $\mathcal{L}(CFRE)$. 
\end{thm}

\begin{thm}
A picture language L is in REC iff it is the projection of a language in $\mathcal{L}(CFRE)$. 
\end{thm}

\begin{thm}
$\mathcal{L}(CFRE) \subsetneq REC$
\end{thm}

\begin{thm}
Neither $\mathcal{L}(SFRE)$ nor $\mathcal{L}(RE)$ does coincide with REC. 
\end{thm}

\end{frame}

\begin{frame}[allowframebreaks]
\frametitle{Regular picture languages}

$R_4 = \{\ominus, \rotatebox{90}{$\ominus$}, *\ominus, *\rotatebox{90}{$\ominus$}, \cup\}$

\begin{define}[REG \cite{matz2007recognizable}]
The family of languages only using operators in $R_4$ is called REG. 
\end{define}

\begin{thm}
REG is closed under: 

\begin{itemize}
	\item union
	\item row and column catenation and closure
	\item projection
\end{itemize}
\end{thm}

\begin{thm}
The membership and emptiness problem for REG is decidable in polynomial time. 
\end{thm}

\begin{thm}
$REG \subsetneq \mathcal{L}(CFRE) \subsetneq REC$
\end{thm}

There are attempts, stating that REG is the better candidate for a definition of ``regular'' picture languages.  These statements are based on the fact, that the languages in REC are as ``complex'' as context-free string languages. 

\end{frame}

\begin{frame}[allowframebreaks]
\frametitle{Diagonal concatenation}

If we consider $\Sigma = \{a\}$ as a one letter alphabet, we only speak about the shape of the pictures. Therefore we can introduce a new operation called \emph{diagonal concatenation} (\rotatebox{135}{$\ominus$}), which concatenates pictures diagonally. 

\begin{define}[Diagonal concatenation]
$p, q \in \Sigma^{**}$ with size of p and q (n, m), (n', m') respectively. Then

\[p \rotatebox{135}{$\ominus$} q = \begin{tabular}{|c|c|}
\hline
p & \\
\hline
 & q \\
\hline
\end{tabular}\]

\end{define}

Thus, p \rotatebox{135}{$\ominus$} q creates a picture over $\{a\}$ of size (n + n', m + m'). 

The closure of diagonal concatenation is denoted by *\rotatebox{135}{$\ominus$}. 

\pagebreak

$R_5 = \{\cup, \rotatebox{135}{$\ominus$}, *\rotatebox{135}{$\ominus$}\}$

\begin{define}
The class of languages over one letter alphabet using operators from $R_5$ is called $\mathcal{L}(D)$. 
\end{define}

\begin{thm}
$\mathcal{L}(D)$ is closed under intersection and complement. 
\end{thm}

\begin{thm}
$\mathcal{L}(CFRE) \subsetneq \mathcal{L}(D)$ for one letter alphabet. 
\end{thm}

\end{frame}

\begin{frame}
\frametitle{Example}

\begin{Example}
$\alpha = ((a)^{\rotatebox{135}{$\ominus$}})^{*\rotatebox{135}{$\ominus$}}$
\end{Example}

Then $L(\alpha) = \{p \in \{a\}^{**} \mid l_1(p) = l_2(p) \text{ and } l_1(p) \text{ is even}\}$ is the language over square shaped pictures with even side-length. 

\end{frame}

\begin{frame}
\frametitle{CRD-regular expressions}

$R_6 = \{\cup, \ominus, \rotatebox{90}{$\ominus$}, *\ominus, *\rotatebox{90}{$\ominus$}, \rotatebox{135}{$\ominus$}, *\rotatebox{135}{$\ominus$}\}$

\begin{define}[CRD-regular expressions]
The class of languages over one letter alphabet using operators from $R_6$ is called $\mathcal{CRD}$. 
\end{define}

\begin{thm}
$\mathcal{L}(CRD) \subsetneq REC$
\end{thm}

\end{frame}

\begin{frame}
\frametitle{Example}

\begin{Example}
$\alpha = (a \rotatebox{90}{$\ominus$} a)^{*\rotatebox{135}{$\ominus$}}$
\end{Example}

Then $L(\alpha) = \{p \in \{a\}^{**} \mid 2 \cdot l_1(p) = l_2(p)\}$ is the language with pictures of size (n, 2n). 

\end{frame}

\begin{frame}[allowframebreaks]
\frametitle{Another operator}

Instead of usual concatenation, we will introduce another operator, which can concatenate eighter before or behind the regular expression. 

\begin{define}
$(\rotatebox{90}{$\ominus$}r), (r\rotatebox{90}{$\ominus$}), (\ominus r), (r\ominus)$ are operators, concatening behind, before, below and on top of a picture, respectively. 
\end{define}

If unrestricted, these operators exceed the class REC. For example $ab((a\rotatebox{90}{$\ominus$})(\rotatebox{90}{$\ominus$}b))^*$ creates the language $\{a^ib^i \mid i \geq 1\}$ which is not in REC. 

\pagebreak

\begin{thm}
If an operator working on the left (or top) is never juxtaposed, intersected or united with an operator working on the right (or bottom), the class of languages created by these operators is included in REC. 
\end{thm}

It is still open, wheter this inclusion is proper or not. 

\end{frame}